package com.zjsru.leetcode75.level1;

import java.util.Arrays;

/**
 * @Author: cookLee
 * @Date: 2023-11-26
 * 咒语和药水的成功对数
 * 同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等于 success ，那么它们视为一对 成功 的组合。
 */
public class SuccessfulPairs {

    /**
     * 主
     * \
     * 输入：spells = [5,1,3], potions = [1,2,3,4,5], success = 7
     * 输出：[4,0,3]
     * 解释：
     * - 第 0 个咒语：5 * [1,2,3,4,5] = [5,10,15,20,25] 。总共 4 个成功组合。
     * - 第 1 个咒语：1 * [1,2,3,4,5] = [1,2,3,4,5] 。总共 0 个成功组合。
     * - 第 2 个咒语：3 * [1,2,3,4,5] = [3,6,9,12,15] 。总共 3 个成功组合。
     * 所以返回 [4,0,3] 。
     * \
     * 输入：spells = [3,1,2], potions = [8,5,8], success = 16
     * 输出：[2,0,2]
     * 解释：
     * - 第 0 个咒语：3 * [8,5,8] = [24,15,24] 。总共 2 个成功组合。
     * - 第 1 个咒语：1 * [8,5,8] = [8,5,8] 。总共 0 个成功组合。
     * - 第 2 个咒语：2 * [8,5,8] = [16,10,16] 。总共 2 个成功组合。
     * 所以返回 [2,0,2] 。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        SuccessfulPairs successfulPairs = new SuccessfulPairs();
        int[] spells = new int[]{5, 1, 3};
        int[] potions = new int[]{1, 2, 3, 4, 5};
        long success = 7;
        System.out.println(Arrays.toString(successfulPairs.successfulPairs2(spells, potions, success)));
    }

    /**
     * 成功对:双循环模拟
     * 如果测试样本很大有int溢出或者是超限的风险
     *
     * @param spells  法术
     * @param potions 药水
     * @param success 成功
     * @return {@link int[]}
     */
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int[] ans = new int[spells.length];
        for (int i = 0; i < spells.length; i++) {
            int count = 0;
            for (int j = 0; j < potions.length; j++) {
                if ((long) spells[i] * potions[j] >= success) {
                    count++;
                    //每次更新
                    ans[i] = count;
                }
            }
        }
        return ans;
    }

    /**
     * 成功配对2：二分法
     *
     * @param spells  法术
     * @param potions 药水
     * @param success 成功
     * @return {@link int[]}
     */
    public int[] successfulPairs2(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);
        int spellLength = spells.length;
        int potionsLength = potions.length;
        int[] ans = new int[spellLength];
        for (int i = 0; i < spellLength; i++) {
            //获取最低限度的值
            long target = (success + spells[i] - 1) / spells[i] - 1;
            //获取target最低限度所在的下标志，potions-最低目标的下标值即是成功的对数
            ans[i] = potionsLength - this.binarySearch(potions, 0, potionsLength - 1, target);
        }
        return ans;
    }

    /**
     * 二进制搜索:
     *
     * @param potions 药水
     * @param target  目标
     * @param left    左
     * @param right   右侧
     * @return int
     */
    private int binarySearch(int[] potions, int left, int right, long target) {
        int ans = right + 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if (potions[mid] > target) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

}
